第五章 优化程序性能

这一章主要讲的是编译器对代码的一些优化策略,包括在代码效率和代码在一些极端状况下的准确性的权衡.以及用具体的汇编代码及在机器中的实现来说明一些代码习惯的对程序效率的影响,最后介绍了一种unix环境下的程序剖析(profiling)工具GPROF.

优化程序的效率时,除了优化整个算法的时间复杂度,其中编译器对代码的编译也起到了至关重要的作用,而编译器除了要将代码变得更快,还需要考虑程序的正确性,开头的例子给出了一个对源代码非常明显的优化,但是编译器却不敢执行这个优化,主要原因就是他不能保证这个优化过的结果和没优化的结果是一样的,事实上,在极端情况下,优化后的代码可能会产生和原来的代码不同的结果.

所以,编译器的一些优化级别,需要保证对程序只使用安全的优化,也就是保证优化后的代码和之前的代码完全相同,这种保证就会使得一些明显的优化无法执行(因为无法保证极端情况下的正确性).

接下来以一个程序(P330)为示例,讲了几种写代码时的优化策略

消除循环的低效率

这个说的是可能编程中经常会遇到的问题,循环 for(int i = 0;i<vec_length(v),++i) 如果这么写的话,每次循环结束都会调用 vec_length() 这个函数来确定是否到达循环结束,对于长度不变的数据结构的遍历,每次循环结束调用的这个函数的开销是不必要的,应将其避免

减少过程调用

这个部分说的是尽量不要在循环中循环调用一些函数,在循环外拿到需要循环遍历的数据结构,然后再循环中直接去调用数据结构.

书中也提到了这种做法不太符合程序模块化的要求,只有在追求效率的代码中会用到,这种情况也应该写几行注释注明.

消除不必要的存储器引用

讲的是,这么写

for(int i = 0;i<length;++i)
    acc = acc OP data[i];

和这么写

for(int i = 0;i<length;++i)
    *dest = *dest OP data[i];

前者更好,因为,前者在汇编中实现可以用寄存器存储 acc ,而后者是个指针,汇编中只能用存储器实现,每次去地址再取指会浪费大量时间.

优化程序的两个限制:

1. 延迟界限: 从开始到结束完全完成一条指令所需要的时间决定,达到这个界限的原因是下一条指令需要上一条指令执行完毕才能执行,指令间有严格的操作顺序.
2. 吞吐量界限: 指令之间可以完全流水线化(fully pipelined),这样使得硬件的功能达到了最大的利用率,在这种情况下优化只能优化处理器功能单元的原始计算能力了.

一些编译器可能做的优化

循环展开

就是循环每次原来读一个数,优化后每次读 k 个数,这样循环的次数就变成了 [n/k] 次,这样优化结果性能的提升得益于 减少了循环的开销工作 ,比如原来累加器 iter 原来要累加 n 次,现在只要累加 [n/k] 次了, 降低了开销操作的数量.

提高并行性

这个比较容易理解,比如一个累加的程序,原来只有一个累加器,每次加一个数,改成并行的可以有 k 个累加器, k 个累加器同时工作肯定要比原来效率高

不过这里硬件会成为限制条件,后面就提到了寄存器溢出这种情况,就是累加器多得在寄存器里面存不下了,只能到栈里面存,这样又增加了存储器开销,反而会使效率下降.

重新结合变换

就是利用有结合律的变换,运用一下结合律,比如把下面这个

acc = acc OP data[i] OP data[i+1]

变成下面这个

acc = add OP (data[i] OP data[i+1])

代码层面没有改进,但是从汇编层面分析,原来每次循环在 acc 上的运算 由原来的两次变成了一次,这样就缩短了关键路径,从而提高了效率.

---

上一章可以看到分支预测会对程序效率有很大影响,因为是一个完全投机的预测,预测错了下面所有取到的指令都应该放弃,这会造成比较大的损失.但是这也是不可避免的,文中提到了 1. 不要过分关心可预测的分支,我们预测分支往往会执行是因为,再循环中,这样的预测策略只有最后一次会失败,所以几率还是比较大的 2. 在程序猿的角度,将分支跳转指令改为条件传送指令( val = exp?a:b; )往往能取得比较好的效果,因为条件传送指令不会有错误的开销: 在流水线中,下一条指令译码钱,上一条指令已经完成了执行操作,因此下一条如果是条件传送指令的话,刚好可以通过转发机制得到状态码.

加载和存储

读和写都制约程序的运行效率 如下:

1. 加载相关, 循环两次之间的读有相关性,下一次的读需要上一次读出来的结果,所以下一条读的指令必须等上一次循环完全结束
2. 读写相关(write/read dependency), 一个存储器读的结果依赖于一个最近的存储器写.这个是经常会遇到的问题.

读写相关的解决方案 (P366):

在存储单元中有个存储缓冲区,包含将会写到存储单元的,但是还没完成的操作(地址,值). 每次读的时候 (load 指令)会先检查一下存储缓冲区,如果发现读的地址在存储缓冲区里面(说明呆会会被写进新值),就直接在存储缓冲区里面拿新值了.

…其实上面的操作就是转发

最后 程序剖析(profiling)

这里介绍了一种分析程序效率的工具,GPROF

1. 在编译和链接过程中加上剖析的指令 gcc -o1 -pg prog.c prog
2. 执行程序,会生成一个多余的 gmon.out 的文件 ./prog arguments...
3. 使用GPROF来解析这个out文件(必须有out文件才能解析) gprof prog